import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: xiaotutu
 * Date: 2024-11-22
 * Time: 10:03
 */
public class BinaryTree {

    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    // 前序遍历
    public void preOrder(TreeNode root) {
        if(root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 前序非递归遍历
    public List<Character> preOrderNor(TreeNode root) {
        List<Character> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);         // 根先入栈
        while(!stack.isEmpty()) {
            TreeNode top = stack.pop(); // 弹出栈顶元素
            res.add(top.val);
            if (top.right != null) stack.push(top.right); // 右子树入栈
            if (top.left != null) stack.push(top.left); // 左子树入栈
        }
        return res;
    }
    //中序遍历
    public void inOrder(TreeNode root) {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    // 中序非递归遍历
    public List<Character> inOrderNor(TreeNode root) {
        List<Character> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;  //一直入栈，然后向左
            }
            cur = stack.pop(); //弹出根元素
            res.add(cur.val); //添加元素
            cur = cur.right;   //向右

        }
        return res;
    }
    //后序遍历
    public void postOrder(TreeNode root) {
        if(root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    //后序非递归遍历
    public List<Character> postOrderNor(TreeNode root) {
        List<Character> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> stack1 = new ArrayDeque<>();
        Deque<TreeNode> stack2 = new ArrayDeque<>();
        stack1.push(root);
        while(!stack1.isEmpty()) {
            TreeNode cur = stack1.pop();
            stack2.push(cur); //倒序收集
            if (cur.left != null) stack1.push(cur.left);
            if (cur.right != null) stack1.push(cur.right);
        }
        while(!stack2.isEmpty()) {
            res.add(stack2.pop().val);
        }
        return res;
    }
}
